# 路径总和

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        if not root:
            return False
        for i in self.visit(root):
            if i == targetSum:
                return True
        return False

    def visit(self, root):
        if not root:
            return -1

        leftlist = self.visit(root.left)
        rightlist = self.visit(root.right)

        list = []

        # 判断是否是叶子结点
        if leftlist == -1 and rightlist == -1:
            list.append(root.val)
            return list

        if leftlist != -1:
            for i in range(len(leftlist)):
                list.append(leftlist[i] + root.val)

        if rightlist != -1:
            for j in range(len(rightlist)):
                list.append(rightlist[j] + root.val)

        # 删除重复元素
        result = []
        for i in list:
            if i not in result:
                result.append(i)

        return result
